// 给定一个二维矩阵，计算其子矩形范围内元素的总和，
// 该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。

class NumMatrix {
    private preSumMatrix: number[][];
    private row: number;
    private col: number;
    constructor(matrix: number[][]) {
        this.row = matrix.length;
        this.col = this.row && matrix[0].length;// 短路运算保证矩阵存在
        // 初始化前缀和矩阵
        this.preSumMatrix = new Array(this.row + 1).fill(0)
            .map(() => new Array(this.col + 1).fill(0));
        // 计算矩阵前缀和，由上方和左方元素推导
        for (let i = 0; i < this.row; i++) {
            for (let j = 0; j < this.col; j++) {
                this.preSumMatrix[i + 1][j + 1] =
                    this.preSumMatrix[i][j + 1] + this.preSumMatrix[i + 1][j] + matrix[i][j]
                    - this.preSumMatrix[i][j];
            }
        }
    }
    // 根据前缀和计算范围和的公式 右下等于 右下减去左减去上加上左上（被减了两遍）
    sumRegion(row1: number, col1: number, row2: number, col2: number): number {
        return this.preSumMatrix[row2 + 1][col2 + 1] - this.preSumMatrix[row2 + 1][col1]
            - this.preSumMatrix[row1][col2 + 1] + this.preSumMatrix[row1][col1];
    }
}


// 很容易看出今天这道题目也是一道前缀和求解相关的题目
// 我们先从如何求出二维空间的 preSum[i][j]。
// 我们定义 preSum[i][j] 表示 从 [0,0]位置到 [i,j] 位置的子矩形所有元素之和。
// 这里最好画一张图来理解...
// 注意这里求前缀和的过程中需要减去左上角的相邻元素，因为它们被计算了两次
// 之后需要根据 preSum 求子矩形面积，如何利用 preSum[i][j] 来快速求出任意子矩形的面积。
// 这里存在一个公式（通过画图推导）：
// preSum[row2][col2] − preSum[row2][col1−1] − preSum[row1−1][col2] + preSum[row1−1][col1−1]
// 其中也是涉及到了算重复或减多了的位置。
